import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by L.jp
 * Description:请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 实现 MyStack 类：
 *
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

 * User: 86189
 * Date: 2022-02-14
 * Time: 20:56
 */

/*  思路：两个队列实现栈的功能，也就是最后一个进来的元素要先出栈，也就是队列里的元素排列要跟栈一样，这样栈从栈顶出也就是队列从队头出，出的是一样的元素
         只要我们实现了队列的压入操作跟栈的元素排布一样，那么对于其他的pop,top和isempty就直接和栈操作是一样的
         主要是push操作

         那么怎么利用两个队列实现栈的压入操作才能保证弹出元素和栈的弹出元素是一样的呢？
         我们定义q1、q2，q1为主队列也就是栈，q2是辅助实现栈的队列，是 q1的临时拷贝
         压入元素是，就是先把元素入q2,然后判断q1是否为空，为空就交换q1和q2，这样元素顺序也不会乱，
         q1不为空的时候，把q1的元素弹出加入到q2,直到q1为空，这样就实现了元素排布和栈是一样的
*
* */
 class MyStack {

    //双队列实现：

    private  Queue<Integer> q1=new LinkedList<>();
    private  Queue<Integer> q2=new LinkedList<>();
    public MyStack() {

    }

    public void push(int x) {
       q2.offer(x); //每次把元素入到q2
       //然后判断q1是否为空，为空就交换，不为空就把q1的元素弹出到q2，直到为空，这样就实现了最后一个进来的在最前面
       while(!q1.isEmpty()){
          q2.offer(q1.poll());
       }
       //为空就交换
       Queue<Integer> temp= q1;
       q1=q2;
       q2=temp;
    }

    public int pop() {
       //实现了栈的元素排布，直接弹出队头元素
       return  q1.poll();

    }

    public int top() {
       return q1.peek();

    }

    public boolean empty() {
       return  q1.isEmpty();

    }
}
